package com.jwetherell.my.problems.misc;

public class FindGroupsOfOneInAMatrix {

//	private int[][] input = new int[][] { { 1, 0 }, { 1, 0 }, { 1, 0 }, { 1, 1 },
//			{ 1, 1 } };
	private int[][] input = new int[][] { { 1, 1, 0, 0, 1 }, { 1, 0, 0, 1, 0 }, { 1, 1, 0, 1, 0 }, { 0, 0, 1, 0, 0 }};
	
	
	private int VISITED = -1;

	public static void main(String[] args) {

		FindGroupsOfOneInAMatrix sol = new FindGroupsOfOneInAMatrix();
		sol.find();

	}

	private void find() {
		
		int oneGroups = 0;
		int zeroGroups = 0;
		
		for (int i=0; i<input.length; i++)
			for (int j=0; j<input[i].length; j++) {
				if (input[i][j] != VISITED) { // means node is not visited
					if (input[i][j] == 0)
						zeroGroups++;
					else if (input[i][j] == 1)
						oneGroups++;
					visitAllMembersInTheGroupRecursively(i,j);
					System.out.println();
				}
			}

		System.out.println("Zero groups: " + zeroGroups);
		System.out.println("One groups: " + oneGroups);
	}

	private void visitAllMembersInTheGroupRecursively(int i, int j) {
		if (input[i][j] != VISITED) {
			System.out.print("(" + i + "," + j + ")");

			int value = input[i][j];
			input[i][j] = VISITED;
			
			if (i-1 >= 0 && input[i-1][j]==value)
				visitAllMembersInTheGroupRecursively(i-1,j);
			if (i+1 < input.length && input[i+1][j]==value)
				visitAllMembersInTheGroupRecursively(i+1,j);
			if (j-1 >= 0 && input[i][j-1]==value)
				visitAllMembersInTheGroupRecursively(i,j-1);
			if (j+1 < input[i].length && input[i][j+1]==value)
				visitAllMembersInTheGroupRecursively(i,j+1);

		}
	}
}
